package com.lkn.datastructure.searching;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 查找和排序
 * @author albert
 *
 * @param <T>
 */
public class SearchingAndSorting<T extends Comparable<T>>{
	/**
	 * 线性查找
	 * @param data 查找的数据
	 * @param min  最小值
	 * @param max  最大值 
	 * @param target 目标元素
	 * @return
	 */
	public static <T extends Comparable<? super T>> boolean linearSearch(T[]data,int min,int max,T target){
		int index = min;
		boolean found = false;
		
		while (!found&&index<=max) {
			if (data[index].compareTo(target)==0) {
				found=true;
			}
			index++;
		}
		return found;		
	}
	/**
	 * 二分查找
	 * @param data 查找的数据
	 * @param min  最小值
	 * @param max  最大值 
	 * @param target 目标元素
	 * @return
	 */
	public static <T extends Comparable<? super T>> boolean binarySearch(T[]data,int min,int max,T target){
		boolean found = false;
		int mid = (min+max)/2;
		if(data[mid].compareTo(target)==0){
			found = true;
		}else if(data[mid].compareTo(target)>0) {
			if (min<mid-1) {
				found = binarySearch(data, min, mid-1, target);
			}
		}else if (mid+1<=max) {
			found = binarySearch(data, mid+1, max, target);
		}
		return found;
	}
	/**
	 * 选择排序
	 * @param data 要排序的数组
	 */
	public static <T extends Comparable<? super T>> void selectionSort(T[]data){
		int min ;
		T temp;
		for (int index = 0; index < data.length-1; index++) {
			min=index;
			for (int scan = index+1; scan < data.length; scan++) {
				if(data[scan].compareTo(data[min])<0){
					min=scan;
				}
			}
			temp = data[min];
			data[min] = data[index];
			data[index]=temp;
		}
	}
	/**
	 * 互换元素
	 * @param data 
	 * @param index1 
	 * @param index2
	 */
	private static <T extends Comparable<? super T>> void swap(T[] data,int index1,int index2) {
		T temp = data[index1];
		data[index1]=data[index2];
		data[index2]=temp;
	}
	/**
	 * 插入排序
	 * @param data
	 */
	public static <T extends Comparable<? super T>>void insertSort(T[]data){
		for (int index = 0; index < data.length; index++) {
			T key = data[index];
			int position = index;
			while (position>0&&data[position-1].compareTo(key)>0) {
				data[position]=data[position-1];
				position--;
			}
			data[position]=key;
		}
	}
	/**
	 * 冒泡排序
	 * @param data
	 */
	public static <T extends Comparable<? super T>>void bubbleSort(T[] data){
		int position,scan;
//		T temp;
		for (position = data.length-1; position >=0 ; position--) {
			for (scan = 0;  scan <= position-1; scan ++) {
				if(data[scan].compareTo(data[scan+1])>0){
					swap(data, scan, scan+1);
				}
			}
		}
	}
	/**
	 * 快速排序
	 * @param data
	 */
	public static <T extends Comparable<T>> void quickSort(T[]data){
		quickSort(data,0,data.length-1);
	}
	/**
	 * 快速排序内部方法
	 * @param data
	 * @param min
	 * @param max
	 */
	private static <T extends Comparable<T>> void quickSort(T[]data,int min,int max){
		if (min<max){
			int indexofpartition = partition(data,min,max);
			quickSort(data, min, indexofpartition-1);
			quickSort(data,indexofpartition+1,max);
		}
	}
	/**
	 * 分区
	 * @param data
	 * @param min
	 * @param max
	 * @return
	 */
	private static <T extends Comparable<T>> int partition(T[]data,int min,int max){
		T partitionElement;
		int left,right;
		int middle = (min+max)/2;
		partitionElement=data[middle];
		swap(data, middle, min);
		left=min;
		right=max;
		while(left<right){
			while(left<right&&data[left].compareTo(partitionElement)<=0){
				left++;
			}
			while(data[right].compareTo(partitionElement)>0){
				right--;
			}
			if(left<right){
				swap(data, left, right);
			}
		}
		swap(data, min, right);
		return right;
	}
	/**
	 * 归并排序
	 * @param data
	 * @param min
	 * @param max
	 */
	public static<T extends Comparable<T>> void mergeSort(T[]data,int min,int max){
		if(min<max){
			int mid=(min+max)/2;
			mergeSort(data, min, mid);
			mergeSort(data, mid+1, max);
			merge(data, min, mid,max);
		}
	}
	/**
	 * 归并排序内部
	 * @param data
	 * @param first
	 * @param mid
	 * @param last
	 */
	public static<T extends Comparable<T>> void merge(T[]data,int first,int mid, int last){
		@SuppressWarnings("unchecked")
		T[]temp = (T[])(new Comparable[data.length]);
		int first1 = first,last1=mid;
		int first2 = mid+1,last2=last;
		int index=first1;
		
		while(first1<=last1&&first2<=last2){
			if(data[first1].compareTo(data[first2])<0){
				temp[index]=data[first1];
				first1++;
			}else{
				temp[index]=data[first2];
				first2++;
			}
			index++;
		}
		while(first1<=last1){
			temp[index]=data[first1];
			first1++;
			index++;
		}
		while(first2<=last2){
			temp[index]=data[first2];
			first2++;
			index++;
		}
		for (index = first; index <= last; index++) {
			data[index]=temp[index];
		}
	}
	/**
	 * 基数排序
	 */
	public static void radixSort(){
		int[]list = {7843,4114,6341,5113,4221,1512,4121,9820,8799,1212};
		String temp;
		Integer numObj;
		int digit,num;
		
		@SuppressWarnings("unchecked")
		Queue<Integer>[] digitQueues = (LinkedList<Integer>[])(new LinkedList[10]);
		for(int digitVal = 0;digitVal<=9;digitVal++){
			digitQueues[digitVal]=(Queue<Integer>)(new LinkedList<Integer>());
		}
		for(int position=0;position<=3;position++){
			for(int scan=0;scan<list.length;scan++){
				temp = String.valueOf(list[scan]);	
				digit=Character.digit(temp.charAt(3-position), 10);
				digitQueues[digit].add(new Integer(list[scan]));
			}
			num=0;
			for(int digitVal=0;digitVal<=9;digitVal++){
				while(!(digitQueues[digitVal].isEmpty())){
					numObj = digitQueues[digitVal].remove();
					list[num]=numObj.intValue();
					num++;
				}
			}
		}
		for(int scan=0;scan<list.length;scan++){
			System.out.println(list[scan]);
		}
	}
}
